package leetcode.editor.cn.dsa04_queue;
//写一个 RecentCounter 类来计算特定时间范围内最近的请求。

public class NumberOfRecentCalls933_3 {
    public static void main(String[] args) {
        RecentCounter recentCounter = new NumberOfRecentCalls933_3().new RecentCounter();
        System.out.println(recentCounter.ping(1)); //1
        System.out.println(recentCounter.ping(100)); //2
        System.out.println(recentCounter.ping(3001)); //3
        System.out.println(recentCounter.ping(3002)); //3
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 最优解：队列解法
     * 1.使用链表实现一个队列
     *   定义属性：队头-head、队尾-tail、长度-size
     *   定义方法：添加节点-add(int)、移除节点-poll() 、队列长度-size()
     *   空间优化：数组的有效请求只有3001个，只需要定义3001容量空间
     * 2.每次请求向队列尾部追加节点
     * 3.循环检查队头数据是否合法，不合法则移除该节点
     * 4.返回队列长度
     */
    class MyQueue { // 1.使用链表实现一个队列
        Node head;
        Node tail;
        int size = 0;
        public void add (int x) { // 入队
            Node newNode = new Node(x);
            if (tail == null) { // 第一次添加数据
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode; // 前一个节点指向新节点
                tail = tail.next; // 尾指针指向新节点
            }
            size++;
        }
        public int poll () { // 出队
            int headVal = head.val; // 获取头节点的数据
            Node next = head.next; // 取出下一个节点
            head.next = null; // 头节点指向null
            head = next; // 头指针指向新节点
            if (next == null) { // 队列中的最后一个元素
                tail = null; // 处理尾指针
            }
            size--;
            return headVal;
        }
        public int peek() { // 查看队头元素值
            return head.getVal();
        }
        public int size () {
            return size;
        }

        class Node { // 队列节点：链表结构
            int val;
            Node next;
            Node(int x) {
                val = x;
            }
            int getVal() {
                return val;
            }
        }
    }
    class RecentCounter {
        MyQueue queue;
        public RecentCounter() {
            queue = new MyQueue();
        }

        public int ping(int t) {
            // 2.每次请求向队列尾部追加节点
            queue.add(t);
            // 3.循环检查队头数据是否合法
            while (queue.peek() < t - 3000) {
                queue.poll();
            }
            // 4.返回队列长度
            return queue.size;
        }
    }
    /**
     * Your RecentCounter object will be instantiated and called as such:
     * RecentCounter obj = new RecentCounter();
     * int param_1 = obj.ping(t);
     */
    //leetcode submit region end(Prohibit modification and deletion)
}